/**
 * @param {number} n
 * @return {number}
 */
var checkRecord = function (n) {
  const MAX = 1000000007
  let count = 0
  let res = [], arr = []
  countA = 1
  countL = 2
  bc(0)

  function bc(index) {
    if (arr.length == n) {
      res.push([...arr.join('')])
      count = (count++)%MAX
      return
    }

    for (let i = index; i < n; i++) {
      arr.push('P')
      bc(i + 1)

      arr.pop()
      if (countA == 1) {
        arr.push('A')
        countA--
        bc(i + 1)
        countA++
        arr.pop()
      }

      if (countL > 0) {
        arr.push('L')
        countL--
        bc(i + 1)
        countL++
        arr.pop()
      }
    }
  }

  return count
};

checkRecord(3)